//class Solution
//{
//public:
//	int halveArray(vector<int>& nums)
//	{
//		priority_queue<double> heap; 
//		double sum = 0.0;
//		for (int x : nums) 
//		{
//			heap.push(x);
//			sum += x;
//		}
//		sum /= 2.0; 
//		int count = 0;
//		while (sum > 0) 
//		{
//			double t = heap.top() / 2.0;
//			heap.pop();
//			sum -= t;
//			count++;
//			heap.push(t);
//		}
//		return count;
//	}
//};




//class Solution
//{
//public:
//	string largestNumber(vector<int>& nums)
//	{
//		vector<string> strs;
//		for (int x : nums) strs.push_back(to_string(x));
//		sort(strs.begin(), strs.end(), [](const string& s1, const string& s2)
//			{
//				return s1 + s2 > s2 + s1;
//			});
//		string ret;
//		for (auto& s : strs) ret += s;
//		if (ret[0] == '0') return "0";
//		return ret;
//	}
//};



class Solution
{
public:
	int lengthOfLIS(vector<int>& nums)
	{
		int n = nums.size();
		vector<int> ret;
		ret.push_back(nums[0]);
		for (int i = 1; i < n; i++)
		{
			if (nums[i] > ret.back()) 
			{
				ret.push_back(nums[i]);
			}
			else
			{
				int left = 0, right = ret.size() - 1;
				while (left < right)
				{
					int mid = (left + right) >> 1;
					if (ret[mid] < nums[i]) left = mid + 1;
					else right = mid;
				}
				ret[left] = nums[i]; 
			}
		}
		return ret.size();
	}
};